package com.lihui.exercises;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 功能描述
 *
 * @author wileda
 * @date 2022/11/07  10:42
 */
public class TopK {
    public static int[] topK01(int[] array,int k){
        int[] result = new int[k];
        if(array.length == 0){
            return result;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < array.length; i++) {
            queue.offer(array[i]);
        }

        for (int i = 0; i < k; i++) {
            result[i] = queue.poll();
        }
        return result;
    }

    public static int[] topK(int[] array,int k){
        int[] result = new int[k];
        if(array.length == 0){
            return result;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < array.length; i++) {
            if(i < k){
                queue.offer(array[i]);
            }else {
                if(array[i] < queue.peek()){
                    queue.poll();
                    queue.offer(array[i]);
                }
            }
        }

        for (int i = 0; i < k; i++) {
            result[i] = queue.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int [] array = { 27,15,19,18,28,34,65,49,25,37 };
        int [] result = topK(array, 3);
        System.out.println(Arrays.toString(result));
    }
}
